package com.jiang.daily.Q3292;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/18 22:30
 */
class Solution {
    public int minValidStrings(String[] words, String target) {
        int len = target.length();
        int[] back = new int[len];
        for (String word: words) {
            int[] next = build_next(word, target);
            int w_len = word.length();
            for (int i = 0; i < len; i++) {
                back[i] = Math.max(back[i], next[i + w_len + 1]);
            }
        }
        int[] dp = new int[len + 1];
        Arrays.fill(dp, 1, len + 1, len);
        for (int i = 0; i < len; i++) {
            dp[i + 1] = dp[i + 1 - back[i]] + 1;
            if (dp[i + 1] > len) {
                return -1;
            }
        }
        return dp[len];
    }

    private int[] build_next(String word, String target) {
        String s = word + "#" + target;
        int len = s.length();
        int[] next = new int[len];
        int i = 1;
        int j = 0;
        while (i < len) {
            if (s.charAt(i) == s.charAt(j)) {
                j++;
                next[i] = j;
                i++;
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    next[i] = j;
                    i++;
                }
            }
        }
        return next;
    }
}
